package com.topcoder.srm181;

import java.util.Comparator;
import java.util.PriorityQueue;

public class KiloManX {
	public int leastShots(String[] damageChart, int[] bossHealth) {
		int N = damageChart.length;
		boolean[] visited = new boolean[1<<N];
		PriorityQueue<Node> queue = new PriorityQueue<Node>(10, 
				new Comparator<Node>(){
			public int compare(Node a, Node b) {
				return a.shots - b.shots;
			}
		});
		
		queue.add(new Node(0, 0));
		while (!queue.isEmpty()) {
			Node top = queue.poll();
			if (visited[top.weapon]) continue;
			visited[top.weapon] = true;
			
			if (top.weapon == (1 << N) - 1) return top.shots;
			
			for (int i=0; i<N; i++) {
				if (((top.weapon >> i) & 1) == 1) continue;
				int best = bossHealth[i];
				for (int j=0; j<N; j++) {
					if (i == j) continue;
					int d = damageChart[j].charAt(i) - '0';
					if (((top.weapon>>j)&1)==1 &&  d!=0) {
						int shotNeeded = (bossHealth[i] + d - 1) / d;
						best = Math.min(best, shotNeeded);
					}
				}
				
				queue.add(new Node(top.weapon|(1<<i), top.shots + best));
			}
		}
		
		return -1;
	}
	
	private class Node {
		int weapon;
		int shots;
		public Node(int weapon, int shots) {
			this.weapon = weapon;
			this.shots = shots;
		}
	}
}
